package leetcode.templates.searchs;

public class BinarySearch {

	int doSomething(int num) {
		return 0;
	}

	public int guessNumber(int n) {
		int l = 1, r = n;
		int ans = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			int guess = doSomething(mid);
			if (guess == 0) {
				return mid;
			} else if (guess == -1) {// 在mid左边
				ans = mid;// 一端收集答案
				r = mid - 1;
			} else {// 在mid右边
				ans = mid;
				l = mid + 1;
			}
		}
		return ans;
	}

	// array上找到大于value的最小索引
	public int find(int[] array, int value) {
		int l = 0, r = array.length - 1;
		int ans = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (array[mid] >= value) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return array.length - ans;
	}
}
